#include <stdio.h>
#include <stdlib.h>

int main() {
    int totalTime, workNum;
    scanf("%d %d", &totalTime, &workNum);
    int *workSalary = (int *)malloc(sizeof(int) * workNum);
    int *workTime = (int *)malloc(sizeof(int) * workNum);
    for(int i = 0; i < workNum; i++) {
        scanf("%d %d", &workTime[i], &workSalary[i]);
    }
    int **dp = (int **)malloc(sizeof(int *) * workNum);
    for(int i = 0; i < workNum; i++) {
        dp[i] = (int *)malloc(sizeof(int) * (totalTime + 1));
    }
    for(int i = 0; i < workNum; i++) {
        for(int j = 0; j <= totalTime; j++) {
            dp[i][j] = 0;
        }
    }
    for(int j = 1; j <= totalTime; j++) {
        if (j >= workTime[0]) {
            dp[0][j] = workSalary[0];
        }
    }
    for(int i = 1; i < workNum; i++) {
        for(int j = 1; j <= totalTime; j++) {
            if (j < workTime[i]) {
                dp[i][j] = dp[i-1][j];
            }
            else {
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-workTime[i]] + workSalary[i]) ?
                dp[i-1][j] : (dp[i-1][j-workTime[i]] + workSalary[i]);
            }
        }
    }
    printf("%d", dp[workNum-1][totalTime]);

    free(workTime);
    free(workSalary);
    for(int i = 0; i < workNum; i++) {
        free(dp[i]);
    }
    free(dp);
    return 0;
}